package com.daxue.se;

import org.junit.jupiter.api.Test;

import java.util.HashMap;

/**
 * @author daxue0929
 * @date 2022/08/27
 **/
public class HashMapTest {
    /**
     *
     * 一般如果new HashMap() 不传值，默认大小是 16，负载因子是 0.75， 如果自己传入初始大小 k，
     * 初始化大小为 大于 k 的 2 的整数次方，例如如果传 10，大小为 16
     *
     *
     * HashMap是java集合包下，实现了Map接口的一个键值对的数据结构
     * 在java8之前，其底层的数据结构是数组+链表，在java8上变为数组+连接+红黑树
     * 因为其基于数组实现，HashMap实现了动态扩容机制，默认的扩容因子是0.75，即已经存储占用75%的容量，会进行扩容。变为原来的2倍
     * 如果Hash冲突，会把对应数组下标位置的元素转为一个链表。把新的元素追加到链表中。
     * 在java8上为了提高查询效率引入了红黑树，当链表长度大于8，且数组长度大于64时，会将链表转为红黑树存储。
     * 当红黑树的节点小于6，也会把红黑树重新转为链表。
     *
     * 红黑树呢，是一个平衡二叉树。
     *
     *
     1.8 还有三点主要的优化：
        1. 数组+链表改成了数组+链表或红黑树；
        2. 链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后；
        3. 扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，位置不变或索引+旧容量大小；
        在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；

        1. 防止发生 hash 冲突，链表长度过长，将时间复杂度由O(n)降为O(logn)

        因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环；

        假设链表中已经有了一个
        A 线程在插入节点 a，B线程也在插入，遇到容量不够开始扩容，重新 hash，放置元素，采用头插法，后遍历到的 B 节点放入了头部，这样形成了环

     */




    @Test
    public void mapTest() {
        HashMap<String, Object> map = new HashMap<>();
        map.put("daxue", "大雪");
    }



}
